#include <iostream>
#include <fstream>
#include <vector>

int max_value;
std::vector<int> best_solution;

void backtrack(int n, int c, const std::vector<int>& weights, const std::vector<int>& values, std::vector<int>& solution, int current_weight, int current_value, int index) {
    if (index == n) {
        if (current_value > max_value) {
            max_value = current_value;
            best_solution = solution;
        }
        return;
    }

    if (current_weight + weights[index] <= c) {
        solution[index] = 1;
        backtrack(n, c, weights, values, solution, current_weight + weights[index], current_value + values[index], index + 1);
        solution[index] = 0;
    }

    backtrack(n, c, weights, values, solution, current_weight, current_value, index + 1);
}

int main() {
    std::ifstream inputFile("input.txt");
    std::ofstream outputFile("output.txt");

    if (!inputFile) {
        std::cerr << "无法打开 input.txt 文件" << std::endl;
        return 1;
    }

    if (!outputFile) {
        std::cerr << "无法创建 output.txt 文件" << std::endl;
        return 1;
    }

    int n, c;
    inputFile >> n >> c;

    std::vector<int> weights(n);
    std::vector<int> values(n);
    for (int i = 0; i < n; i++) {
        inputFile >> weights[i];
    }
    for (int i = 0; i < n; i++) {
        inputFile >> values[i];
    }

    std::vector<int> solution(n);
    max_value = 0;

    backtrack(n, c, weights, values, solution, 0, 0, 0);
    
    std::cout << "最优解为：" ;
    for (int i = 0; i < n; i++) {
        outputFile << best_solution[i] << " ";
        std::cout << best_solution[i] << " ";
    }
    outputFile << std::endl;

    inputFile.close();
    outputFile.close();

    std::cout << "\n已写入 output.txt 文件" << std::endl;

    return 0;
}